The field of the invention is evolutionary processes; more particularly, the present invention relates to a method utilizing evolutionary processes for solving partial constraint satisfaction problems in order to produce a near-optimal or optimal sequence of products for manufacture.
The present invention relates to a method for solving partial constraint satisfaction problems, more particularly to a method of sequencing products for manufacture such that the sequence produced is a near-optimal or optimal sequence, meaning that direct cost associated with various labor, processes, and parts inventory are minimized and equipment and floor space utilization are maximized. One application of the method of the present invention is the sequencing of automobiles during manufacturing, in which vehicles are sequenced to go through a series of operations such as body forming, painting, component assembly (such as installing radios, seats, etc.) and final assembly (adding trim and chassis).
The sequencing of manufacturing stages or tasks represents a combinatorial, or partial, constraint satisfaction and optimization problem.
As is understood by those skilled in the art, partial constraint satisfaction problems (PCSP""s), such as scheduling or sequencing, do not lend themselves easily to automated solving. A solution to a PCSP typically must satisfy a set of hard constraints to be valid or feasible, and must minimize the costs associated with violating one or more conflicting soft constraints (i.e., the solution must present the best trade-off among the conflicting soft constraints). The soft constraints cannot be all completely or simultaneously satisfied in a solution. Thus, each soft constraint is allowed to be violated at a cost (i.e., partially satisfied) and the best solution is a valid solution (i.e., satisfying all hard constraints) which minimizes the costs incurred with violating the soft constraints and the degree of violation thereof.
PCSP""s, such as the scheduling (or sequencing) of products for manufacture present a particularly difficult type of problemxe2x80x94a computationally complex problem, referred to as an NP-complete problem (see Garey, M. and Johnson, D. , Computers and intractability: a guide to the theory of NP-completeness, Freeman, 1979.), for which search techniques that deterministically and exhaustively search the space of possibilities fail to generate a viable solution in a realistic time period. For the generic problem of assigning N tasks to M resources with a particular ordering of tasks at each resource, the number of possible solutions is       (                                        N            +            M            -            1                                                            M            -            1                                )    ⁢      xe2x80x83    ⁢      N    !  
which implies super-exponential growth as a function of the number of tasks and resources. In addition to sheer size, this search space has a more complex topology than a Euclidean space or, when M  greater than 1, a space of permutations.
Exhaustive search (for the best sequence) is impractical for most of the real-world sequencing problems which often have a sequence length ranging from the 100""s to the 1000""s and are subject to many conflicting constraints. Traditional algorithmic techniques, such as dynamic programming (see Bellman, R. E., and Dreyfus, S. E., Applied dynamic programming, Princeton University Press, 1962), and branch-and-bounds (see Lawler, E. L., and Wood, D. E., xe2x80x9cBranch and bounds methods: A survey,xe2x80x9d Operations Research, 14, 699-719, 1966) fail due to their lack of scalability. The heuristic methods developed to date are complicated by the details of a particular task, and the algorithmic consideration of the specific constraints is embodied in what amounts to a domain specific expert system. Such heuristic techniques are often highly specific to particular application domains and thus are not useful as general techniques for solving PCSP problems.
Real-world scheduling/sequencing problems present special difficulties not found in the less than real-world problems addressed in the art to date. These difficulties include: (1) the size and complexity of the real-world search space, which is far more formidable than the search typically defined in less than real-world problems; (2) the dynamic process inherent in real-world scheduling/sequencing problems (schedules remain valid only for a limited amount of time; after a certain duration, the world generally has changed enough that the scheduling algorithm has to find a different schedule; additionally, there are time constraints on how long it can take to schedule and reschedule that place limits on the amount of computation that can be performed by a scheduling algorithm; and (3) the different domains and applications present in real-world scheduling problems, which require solutions of different variations of the scheduling problem (these variations arise from a number of different sources, including: differences in the types of hard constraints, such as relative and absolute temporal restrictions, and resource capabilities constraints; the need for additional information beyond an ordered assignment of tasks to resources, such as absolute times, routes traveled, and manufacturing plans; and different sets of evaluation criteria, such as cumulative response time, throughput, time span, and cumulative employee satisfaction.) Real-world scheduling/sequencing algorithms thus must be flexible enough to accommodate different conditions and able to adapt to changes.
Evolutionary computation (abbreviated as xe2x80x9cECxe2x80x9d), a general, stochastic framework inspired by the intrinsically robust search and optimization paradigms of biological evolution, presents the most promising direction in solving real-world PCSP""s. EC algorithms have been applied to many hard optimization problems where classical methods (e.g., gradient search, linear programming, etc.) have failed to provide good solutions. See, e.g.. Back, T., Fogel, D. B., and Michalewicz, Z, eds., Handbook of Evolutionary Computation. New York: Oxford Univ. Press and Institute of Physics, 1997.
All EC algorithms share the same basic high-level philosophy and structure. In any EC algorithm, a xe2x80x9cpopulationxe2x80x9d of individuals, called xe2x80x9cchromosomes,xe2x80x9d is maintained. Each chromosome represents a potential solution to the problem to be solved. An xe2x80x9cinitialization processxe2x80x9d is incorporated to create the initial population (i.e., the first generation of chromosomes). A xe2x80x9cfitness measurexe2x80x9d representing certain optimization criteria is employed to evaluate how fit or optimized each chromosome is, and a xe2x80x9cselection processxe2x80x9d is used to select chromosomes for xe2x80x9creproductionxe2x80x9d based on their fitness values. The reproduction process applies xe2x80x9cgenetic operatorsxe2x80x9d to the selected chromosomes to create probabilistically perturbed variants, called xe2x80x9coffspring,xe2x80x9d among which are likely fitter chromosomes. A unary genetic operator alters a (parent) chromosome in some fashion probabilistically, and is called a xe2x80x9cmutation.xe2x80x9d A binary genetic operator combines probabilistically determined portions of two parent chromosomes to produce two offspring, and is called a xe2x80x9ccrossover.xe2x80x9d The offspring chromosomes are then evaluated by the fitness measure and, based on their values of fitness, are used to replace certain worse chromosomes in the population to form a new generation.
The general EC procedure can be outlined as follows, where t denotes generation index and P(t) denotes the population of chromosomes at t:
Begin
t=0;
Initialization (to create P(t) typically randomly);
Repeat
Fitness evaluation of P(t);
Selection of chromosomes in P(t);
Reproduction to produce a P(t+1);
t=t+1;
Until certain termination condition is satisfied (when t=T)
End.
By repeating the above evaluation-selection-reproduction loop, the population can be xe2x80x9cevolvedxe2x80x9d to fitter populations (Darwinian survival of the fittest). Note that in the process, P(t) remains of the same size, i.e., has the same number of chromosomes. After a certain number of generations (which is either predetermined, or decided based on specified xe2x80x9cterminationxe2x80x9d conditions), the best chromosome in the final population represents the optimal or near-optimal solution to the problem.
Such a EC paradigm is inherently parallel (as a whole population can evolve simultaneously) and robust (as it is a probabilistic or randomized process). It combines exploitation of the most promising search area, through fitness-governed selection and reproduction, and exploration of the broadest search space through randomness.
Such a EC paradigm is also general in the sense that only the fitness function used to evaluate how xe2x80x9cgoodxe2x80x9d a chromosome is requires problem-specific knowledge or information; the other components can be relatively problem-independent. For example, initialization is typically done by randomly generating chromosomes. A typical method of chromosome selection is xe2x80x9croulette wheelxe2x80x9d sampling in which each chromosome is assigned a slice of a circular xe2x80x9croulette wheel,xe2x80x9d with the size of the slice being proportional to the chromosome""s fitness. The wheel can then be spun N times, where N is the number of individuals in the population. On each spin, the individual under the wheel""s marker is selected to be in the pool of parents for the next generation.
On the other hand, one can also design each component of the EC paradigm (as outlined above) differently to suit special needs of a particular problem. Thus, the EC paradigm is both general and flexible.
Indeed, different EC algorithms are characterized by different designs of the basic components: (1) representation of chromosomes, (2) selection strategy, (3) reproduction strategy (including genetic operators), and (4) problem-dependent criteria and method for fitness evaluation of chromosomes. For example, three pioneer classes of EC algorithms, Genetic Algorithms (GAs) (see Holland, J., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975), Evolutionary Programming (EP) (see Fogel, L., et al., Artificial Intelligence through Simulated Evolution, Wiley, New York, 1966), and Evolutionary Strategies (ESs), differ in these components. In GAs, which are perhaps the most influential form of EC algorithms, a chromosome has the structure of a bit string, and crossover is emphasized as a major operation, whereas in EP and ES, a chromosome represents a string of real numbers, and mutation is emphasized.
In early applications of EC, a concrete problem description was typically mapped into a standard, well-known chromosome representation, such as a bit string in a classical GA, and the problem was then solved by a standard, well-known EC algorithm, such as a classical GA. This, however, has many limitations. Although bit string (or binary) representation has facilitated the development of the theoretical foundation of GAs, bit string representation severely limits the range in which the algorithm can operate. It is thus ineffective in problems where the desired solution is hierarchical, or where the size and shape of the solution is unknown in advance. In a classical GA, there is one mutation operator and one crossover operator. The mutation operator flips a randomly selected bit in a chromosome to produce a new offspring. The crossover operator cuts the two chromosomes into two parts at the same (randomly selected) position and swaps the second parts of the two chromosomes to produce two offspring chromosomes. These operations, at the level of bits, usually make evolution too slow in converging to a satisfactory solution.
More recent approaches emphasize the use of xe2x80x9cnaturalxe2x80x9d chromosome structures which best describe the class of problems to be solved, and accordingly, the use of problem-sensitive genetic operators (see Michalewicz, Z. Genetic algorithms+data structures=evolution programs, 3rd ed., Springer-Verlag, 1996). An important question (and problem) inherent in these approaches, however. is to what extent should the problem-specific knowledge or information be embedded in the algorithm to achieve a good balance of efficiency and general applicability. Trying to answer this question well is a continuing struggle for EC practitioners.
Among the problems attacked by EC methods, scheduling problems have drawn considerable attention, see Special Issue: Evolutionary Algorithms for Scheduling, Evolutionary Computation, 6(1), 1998, including the specific problem of car sequencing, see Warwick, T. and Tsang, E. P. K., xe2x80x9cTackling car sequencing problems using a generic genetic algorithm,xe2x80x9d Evolutionary computation, 3(3): 267-298, 1995. However, the car sequencing problems considered to date constitute unrealistically simplified versions of the real-world problem, having no more than one hard constraint and one type of soft constraints. The approaches considered to date are also not suitable for real-world sequencing problems, which have many different kinds of hard and soft constraints, because with multiple constraints, they do not result in a feasible or valid solution within a finite time period. The prior art crossover operator also can result in severe violation of hard constraints in the offspring produced, and repairing the infeasible offspring can be very expensive.
In sum, there is no effective method, EC-based or not, in the prior art which is able to handle the complex real-world sequencing problems successfully. The present invention overcomes the problems and insufficiencies in the art in a novel manner.
In view of the shortcomings and inabilities of the existing methods for solving real-world sequencing problems, the present invention provides a general method of sequencing manufacturing tasks which employs an EC algorithm to determine near-optimal solutions to a partial constraint satisfaction problem (xe2x80x9cPCSPxe2x80x9d). A preferred embodiment comprises a method for determining within a finite time period near-optimal sequencing of manufacturing tasks subject to user-given hard and soft constraints.
It is to be understood that the foregoing general description and the following detailed description are exemplary and explanatory only, and not restrictive of the invention as claimed.